Antialiasing in the context of digitizing line art and certain graphical image structures is best known as a method of using intermediate levels of intensity to achieve subpixel position of edges for several reasons including reduction or elimination of jaggies on the edges of lines and polygons, including text. As used herein the term antialiased is intended to refer to those segments or regions of an image that are effected by an antialiasing operation applied to the image (e.g. an image processing operation or a physical process resulting in gray pixels along the edges of line art or text). Jaggies are, primarily visible at the edges of sloped lines approaching horizontal or vertical. The term antialiasing suggests an analog term aliasing; normally representing the presence of low frequencies resulting from sampling high frequency signals at too low a sampling rate.
Consider a near-vertical (or near-horizontal) line segment. To be perfectly reproduced in a printed media, the phase, which represents the location of the edge, must continuously vary along the length of a segment. Due to the inherent sampling of a bi-level display or printed output, the phase exhibits jump discontinuities. Thus, this form of aliasing artifact, leads to an induced jagged appearance where the structures are referred to as jaggies. Within a sampled image any graphical object is eventually approximated as a polygon or collection of polygons. These polygons have straight edges some of which will exhibit aliasing (jaggies and other placement defects). FIG. 1 for example shows aliasing in two dimensions. When the triangle on the top of FIG. 1 is rasterized, the edges are aliased as reproduced in the triangle shown at the bottom of FIG. 1. In particular, the position along the bottom edge should move up slightly from column to column as one looks from left to right in the image at the bottom of FIG. 1. However, the position is quantized, as illustrated, producing the jagged appearance along the bottom of the triangle. Visibility of the anti-aliased image artifacts is increased by the regular nature of the jaggies, again a result of sampling.
Consider the following systems and their capability, or incapability, to utilize antialiased pixels. Xerox's Docucolor 40, for example, employs a high frequency analog line screen to render antialiased pixels, but that is not an option for some products or marked segments. When conventional screens (e.g., approximately equal to 130-150 CPI dots) are employed in a rendering module, antialiased pixels are halftoned and printed, resulting in objectionable halftone dots positioned along character edges. Hyperacuity printing techniques, for example those described by Curry, et al. (U.S. Pat. No. 5,138,339 and U.S. Pat. No. 5,485,289) can provide rendering for antialiased pixels that is compatible with simultaneously printing dot screen halftones in enhanced line art. However, these techniques require the use of tags to identify the antialiased pixels as antialiased line art. In the preferred embodiments described with respect to the present invention the rendering architecture distinguishes text/line art from contone images to appropriately treat both image types. As will be described herein an algorithm or method may be employed in a rendering module or in other components of the rendering device to convert gray antialiased pixels to a form suitable for xerographic printing.
Antialiased images can be generated by capturing the image at a resolution greater than the final or desired output resolution, then reducing the resolution of the image by sub-sampling using an averaging process. A major benefit of antialiased images is that high contrast, saturated objects are surrounded with pixels possessing intermediate values that visually suggest the true, higher resolution position of object edges.
For example, in binary printing systems, such as many xerographic or ink jet systems that use a halftoning process to simulate continuous tone images, these antialiased edge pixels should be rendered with a very high frequency cell, ideally one having the resolution of the final output image. If the standard system halftone dot were to be used, the antialiased edges would be serrated or jagged at the standard halftone frequency. This rendering would reduce or even negate any value obtained through antialiasing. The use of a very high frequency screen over the entire antialiased image renders the antialiased pixel properly, but tends to sharpen the tonal curve and provoke print quality defects in the overall image.
Antialiasing produces image structures with gray borders or boundaries. Gray borders can also be present in an image due to the nature of a particular image structure. For instance, a gray character on a white background and a white character on a gray background also possess gray borders. As is the case for antialiased edge pixels, it is generally desirable to render the borders for gray objects with a high frequency screen, while is may be desired to render the interior of the gray stroke with a lower frequency screen chosen for attributes other than edge rendition. Through an optimized use of thresholds, these border pixels can be tagged, and subsequently optimally rendered, in a similar manner to border pixels that are gray due to antialiasing. This form of selective rendering will produce a high frequency edge outline at the gray-to-white border (note the border can be also be between two gray levels given the use for adaptive thresholds). Throughout the present discussion both types of border pixels (from gray objects and from antialiased objects) will sometimes be referred to simply as antialiased pixels.
Hence, the present invention is directed to a method for detecting antialiased image regions and creating rendering tags within an architecture designed for the rendering of antialiased text or line regions, thereby enabling the antialiased pixels to be rendered in a manner distinguishable from that applied to continuous tone portions of an image.
Heretofore, a number of patents and publications have disclosed information relevant to antialiasing, the relevant portions of which may be briefly summarized as follows:
U.S. Pat. No. 5,646,751 to Motamed et al., issued Jul. 8, 1997, teaches a method for improving the speed of a color conversion operation using pixel tagging.
In "A Comparison of Antialiasing Techniques," IEEE CG&A, Vol. 1, No. 1, January 1981, pp. 40-48, F. Crow teaches that prefiltering is a computationally effective technique for antialiasing.
U.S. Pat. No. 5,432,898 to Curb et al, issued Jul. 11, 1995, provides a system and method for anti-aliasing of lines within a data processing system having graphics capability, which requires a minimum amount of hardware to implement and does not degrade the performance or speed of the system.
U.S. Pat. No. 5,438,656 to Valdes, et al., issued Aug. 1, 1995, describes a method of synthesizing multi-level raster shapes directly from ideal shapes.
In accordance with the present invention, there is provided an edge-detecting method for detecting antialiased pixels within continuous tone image data representing an image, wherein a logic-based implementation of the edge-detecting method includes the steps of: determining a threshold for a region of the image; in a first channel, setting a threshold to be used to binarize the region of the image, the threshold being determined as a function of a first image criterion, thresholding at least a region of the continuous tone image to create a binarized image region, extracting, from the binarized image region, a vector comprised of a predefined set of pixels within the binarized image region, applying the vector to a first channel logic operation to determine if a predefined pattern is present, and if so, indicating the presence of the pattern as a first channel output;
logically combining the outputs of at least the first channel and the second channel to produce a tag indicative of the presence or absence of a gray border pixel within the region of the image.
In accordance with another aspect of the present invention, there is provided an apparatus for detecting antialiased pixels within continuous tone image data representing an image, including: means for histogramming the continuous tone image data to determine a threshold for a region of the image; a first channel, having a thresholder to binarize the region of the image using a threshold determined as a function of a first image criterion, and create a binarized image region, vector memory for storing a vector comprised of a predefined set of pixels within the binarized image region, the vector being extracted from the binarized image region, a look-up table for receiving the vector from said vector memory, applying the vector to a first channel logic operation to determine if a predefined pattern is present, and if so, indicating the presence of the pattern in an output of the look-up table; a second channel, having a thresholder to binarize a region of the image using a threshold determined as a function of a second image criterion, and create a second binarized image region, second vector memory for storing a second vector comprised of a predefined set of pixels within the second binarized image region, the second vector being extracted from the second binarized image region, a second look-up table for receiving the vector from said second vector memory, applying the vector to a second channel logic operation to determine if a predefined pattern is present, and if so, indicating the presence of the pattern in an output of the second look-up table; a tag map for logically combining the channel outputs to produce a tag indicative of the presence or absence of an antialiased pixel within the region of the image.
In accordance with yet another aspect of the present invention, there is provided a method for identifying thin, gray lines containing antialiased pixels within continuous tone image data representing an image, including the steps of: identifying a subset of image pixels within a window centered about a target pixel; histogramming the pixels within the subset; determining the sense of the target pixel; as a function of the sense of the neighboring window context of the target pixel; determining whether the current pixel is an antialiased pixel; and generating an output tag indicative of the antialiased nature of the target pixel.
In accordance with the present invention, there is provided a method for detecting antialiased pixels within continuous tone image data representing an image, including the steps of: determining a threshold for a region of the image; in a first channel, setting a threshold to be used to binarize the region of the image, the threshold being determined as a function of a first image criterion, such as an image background level, thresholding at least a region of the continuous tone image to create a binarized image region, extracting, from the binarized image region, a vector comprised of a predefined set of pixels within the binarized image region, applying the vector to a first channel logic operation to determine if a predefined pattern is present, and if so, indicating the presence of the pattern as a first channel output;
One aspect of the invention deals with a basic problem in the rendering of antialiased images, particularly text and line art regions--identifying the antialiased regions when present on a non-white (e.g., printed) background and an appropriate technique for rendering the antialiased regions. This aspect is further based on the discovery of improved techniques that are able to detect antialiased fine gray features and the presence of antialiased regions on gray or black backgrounds. The technique is preferably employed in a rendering architecture that distinguishes between image types (e.g., binary text or lines and continuous tone), determines whether a given pixel has been antialiased, tags the pixel, and directs the rendering operation accordingly.
Another aspect of the present invention preferably employs histogramming techniques to determine foreground levels and background levels for the identification of gray objects within the image field, which also may be gray. Once the levels are established, thresholds can be used to distinguish foreground objects from background levels and pattern matching can be employed to identify the presence of particular border patterns. The border pixels are tagged in a similar manner to pixels that are gray due to antialiasing.